package com.algorithm.recursive;

//实现斐波那契数列
//题目：现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
//什么是斐波那契数列？定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
//实例：0、1、1、2、3、5、8、13、21、34、……
public class FibonacciSequence {
    public static void main(String[] args) {
        System.out.printf("循环:"+Fibonacci(4)+"");
        System.out.printf("递归:"+Fibonacci1(4)+"");
    }
    //通过循环的方式实现
    public static int Fibonacci(int n) {
        if(n<2){
            return n;
        }
        int a=0;
        int b=1;
        int t=0;
        for(int i=2;i<=n;i++){
            t=b;
            b=a+b;
            a=t;
        }
        return b;

    }
    //通过递归方式实现
    public static int Fibonacci1(int n) {
        if(n<2){
            return n;
        }
        return Fibonacci1(n-1)+Fibonacci1(n-2);

    }
}
